#include<stdio.h>
#include<iostream>
using namespace std;

//生成树：所有顶点均由边连接在一起，但不存在回路的图 
//一个图可以有许多棵不同的生成树  

//深度优先生成树 
//广度优先生成树 

//最小生成树：给定一个无向网，在该网的所有生成树中，使得 各边权值之和最小的 那棵生成树称为该网的最小生成树, 也叫最小代价生成树 

//Minimum Spanning Tree：MST性质 
//在生成树的构造过程中，图中n个顶点分属两个集合
//		已落在生成树上的顶点集：U
//		尚未落在生成树上的顶点集：V - U
//接下来则应在所有连通U中顶点和 V - U 中顶点的边中选取权值最小的边 
 


//构造最小生成树的方法一：普里姆算法(Prim) 选择点，时间复杂度O(n2) (n为顶点数)， 适合稠密图  
//构造最小生成树的方法二：克鲁斯卡尔算法(Kruskal) 选择边，时间复杂度O(eloge) (e为边数)，适合稀疏图 



